module ai {
	export class NegaMaxSearch extends BaseClass {

		public board: chess.ChessBoard;

		public count: number = 0;
		public ABcut: number = 0;
		public PVcut: number = 0;

		public cacheDic: any = {};
		public cacheCount: number = 0;
		public cacheGet: number = 0;

		public start: any;
		public constructor() {
			super();
		}

		/*
 		* max min search
 		* white is max, black is min
 		*/
		public negamax(candidates, role, deep, alpha, beta) {
			let self = this;
			let config = chess.ChessConst.config;
			self.count = 0
			self.ABcut = 0
			self.PVcut = 0
			self.board.currentSteps = []

			for (let i = 0; i < candidates.length; i++) {
				let p = candidates[i]
				self.board.put(p, role)
				let steps = [p]
				let v = this.deepFirstSearch(deep - 1, -beta, -alpha, chess.ChessConst.role.reverse(role), 1, steps.slice(0), 0)
				v.score *= -1
				alpha = Math.max(alpha, v.score)
				self.board.remove(p)
				p.v = v

				// 超时判定
				if ((+ new Date()) - self.start > config.timeLimit * 1000) {
					Log.trace('timeout...')
					break // 超时，退出循环
				}
			}

			config.log && Log.trace('迭代完成,deep=' + deep)
			config.log && Log.trace(candidates.map(function (d) {
				return '[' + d[0] + ',' + d[1] + ']'
					+ ',score:' + d.v.score
					+ ',step:' + d.v.step
					+ ',steps:' + d.v.steps.join(';')
					+ (d.v.c ? ',c:' + [d.v.c.score.steps || []].join(";") : '')
					+ (d.v.vct ? (',vct:' + d.v.vct.join(';')) : '')
					+ (d.v.vcf ? (',vcf:' + d.v.vcf.join(';')) : '')
			}))

			return alpha
		}

		public deepFirstSearch(deep, alpha, beta, role, step, steps, spread) {
			let config = chess.ChessConst.config;
			config.debug && this.board.logSteps();
			if (config.cache) {
				let c = this.cacheDic[this.board.zobrist.code];
				if (c) {
					if (c["deep"] >= deep) { // 如果缓存中的结果搜索深度不比当前小，则结果完全可用
						this.cacheGet++;
						// 记得clone，因为这个分数会在搜索过程中被修改，会使缓存中的值不正确
						return {
							score: c["score"]["score"],
							steps: steps,
							step: step + c["score"]["step"],
							c: c
						};
					} else {
						// 如果缓存的结果中搜索深度比当前小，那么任何一方出现双三及以上结果的情况下可用
						// TODO: 只有这一个缓存策略是会导致开启缓存后会和以前的结果有一点点区别的，其他几种都是透明的缓存策略
						if (ai.ChessMath.getInstance().greatOrEqualThan(c["score"], chess.ChessConst.score.FOUR) || ai.ChessMath.getInstance().littleOrEqualThan(c["score"], -chess.ChessConst.score.FOUR)) {
							this.cacheGet++;
							return c["score"];
						}
					}
				}
			}

			let _e = this.board.evaluate(role);
			let leaf = {
				score: _e,
				step: step,
				steps: steps
			};
			let T = chess.ChessConst.score;
			let MAX = T.FIVE * 10;
			let MIN = -1 * MAX;
			let R = chess.ChessConst.role;
			this.count++;

			// 搜索到底 或者已经胜利
			// 注意这里是小于0，而不是1，因为本次直接返回结果并没有下一步棋
			if (deep <= 0 || ai.ChessMath.getInstance().greatOrEqualThan(_e, T.FIVE) || ai.ChessMath.getInstance().littleOrEqualThan(_e, -T.FIVE)) {
				//// 经过测试，把算杀放在对子节点的搜索之后，比放在前面速度更快一些。
				//// vcf
				//// 自己没有形成活四，对面也没有形成活四，那么先尝试VCF
				//if(math.littleThan(_e, chess.ChessConst.score.FOUR) && math.greatThan(_e, chess.ChessConst.score.FOUR * -1)) {
				//  mate = vcx.vcf(role, vcxDeep)
				//  if(mate) {
				//    config.debug && Log.trace('vcf success')
				//    v = {
				//      score: mate.score,
				//      step: step + mate.length,
				//      steps: steps,
				//      vcf: mate // 一个标记为，表示这个值是由vcx算出的
				//    }
				//    return v
				//  }
				//} // vct
				//// 自己没有形成活三，对面也没有高于活三的棋型，那么尝试VCT
				//if(math.littleThan(_e, chess.ChessConst.score.THREE*2) && math.greatThan(_e, chess.ChessConst.score.THREE * -2)) {
				//  let mate = vcx.vct(role, vcxDeep)
				//  if(mate) {
				//    config.debug && Log.trace('vct success')
				//    v = {
				//      score: mate.score,
				//      step: step + mate.length,
				//      steps: steps,
				//      vct: mate // 一个标记为，表示这个值是由vcx算出的
				//    }
				//  return v
				//  }
				//}
				return leaf
			}

			let best = {
				score: MIN,
				step: step,
				steps: steps
			}
			// 双方个下两个子之后，开启star spread 模式
			let points = this.board.gen(role, this.board.count > 10 ? step > 1 : step > 3, step > 1)

			if (!points.length) return leaf

			Log.trace('points:' + points.map((d) => '[' + d[0] + ',' + d[1] + ']').join(','));
			Log.trace('A~B: ' + alpha + '~' + beta);

			for (let i = 0; i < points.length; i++) {
				let p = points[i]
				this.board.put(p, role);
				let _deep = deep - 1;
				let _spread = spread;

				if (_spread < chess.ChessConst.config.spreadLimit) {
					// 冲四延伸
					if ((role == R.com && p.scoreHum >= T.FIVE) || (role == R.hum && p.scoreCom >= chess.ChessConst.score.FIVE)) {
						// _deep = deep+1
						_deep += 2
						_spread++
					}
					// 单步延伸策略：双三延伸
					//if ( (role == R.com && p.scoreCom >= chess.ChessConst.score.THREE * 2) || (role == R.hum && p.scoreHum >= chess.ChessConst.score.THREE*2)) {
					//  _deep = deep
					//  _spread ++
					//}
				}

				let _steps = steps.slice(0);
				_steps.push(p);
				let v = this.deepFirstSearch(_deep, -beta, -alpha, R.reverse(role), step + 1, _steps, _spread);
				v.score *= -1;
				this.board.remove(p);


				// 注意，这里决定了剪枝时使用的值必须比MAX小
				if (v.score > best.score) {
					best = v;
				}
				alpha = Math.max(best.score, alpha);
				//AB 剪枝
				// 这里不要直接返回原来的值，因为这样上一层会以为就是这个分，实际上这个节点直接剪掉就好了，根本不用考虑，也就是直接给一个很大的值让他被减掉
				// 这样会导致一些差不多的节点都被剪掉，但是没关系，不影响棋力
				// 一定要注意，这里必须是 greatThan 即 明显大于，而不是 greatOrEqualThan 不然会出现很多差不多的有用分支被剪掉，会出现致命错误
				if (ai.ChessMath.getInstance().greatOrEqualThan(v.score, beta)) {
					chess.ChessConst.config.debug && Log.trace('AB Cut [' + p[0] + ',' + p[1] + ']' + v.score + ' >= ' + beta + '');
					this.ABcut++;
					v.score = MAX - 1; // 被剪枝的，直接用一个极大值来记录，但是注意必须比MAX小
					v.abcut = 1; // 剪枝标记
					// cache(deep, v) // 别缓存被剪枝的，而且，这个返回到上层之后，也注意都不要缓存
					return v;
				}
			}

			this.cache(deep, best);
			return best;
		}

		public cache(deep, score) {
			if (!chess.ChessConst.config.cache) return false;
			if (score.abcut) return false;// 被剪枝的不要缓存哦，因为分数是一个极值
			// 记得clone，因为score在搜索的时候可能会被改的，这里要clone一个新的
			let obj = {
				deep: deep,
				score: {
					score: score.score,
					steps: score.steps,
					step: score.step
				},
				board: this.board.toString()
			}
			this.cacheDic[this.board.zobrist.code] = obj;
			this.cacheCount++;
		}

		public deeping(candidates, role, deep) {
			let config = chess.ChessConst.config;
			let MAX = chess.ChessConst.score.FIVE * 10;
			let MIN = -1 * MAX
			this.start = (+ new Date());
			this.cacheDic = {};// 每次开始迭代的时候清空缓存。这里缓存的主要目的是在每一次的时候加快搜索，而不是长期存储。事实证明这样的清空方式对搜索速度的影响非常小（小于10%)

			let bestScore;
			for (let i = 2; i <= deep; i += 2) {
				bestScore = this.negamax(candidates, role, i, MIN, MAX);
				//// 每次迭代剔除必败点，直到没有必败点或者只剩最后一个点
				//// 实际上，由于必败点几乎都会被AB剪枝剪掉，因此这段代码几乎不会生效
				//let newCandidates = candidates.filter(function (d) {
				//  return !d.abcut
				//})
				//candidates = newCandidates.length ? newCandidates : [candidates[0]] // 必败了，随便走走

				if (ai.ChessMath.getInstance().greatOrEqualThan(bestScore, chess.ChessConst.score.FIVE)) break;// 能赢了
				// 下面这样做，会导致上一层的分数，在这一层导致自己被剪枝的bug，因为我们的判断条件是 >=， 上次层搜到的分数，在更深一层搜索的时候，会因为满足 >= 的条件而把自己剪枝掉
				// if (math.littleThan(bestScore, T.THREE * 2)) bestScore = MIN // 如果能找到双三以上的棋，则保留bestScore做剪枝，否则直接设置为最小值
			}

			// 美化一下
			candidates = candidates.map(function (d) {
				let r = [d[0], d[1]];
				r["score"] = d.v.score;
				r["step"] = d.v.step;
				r["steps"] = d.v.steps;
				if (d.v.vct) r["vct"] = d.v.vct;
				if (d.v.vcf) r["vcf"] = d.v.vcf;
				return r;
			})

			// 排序
			// 经过测试，这个如果放在上面的for循环中（就是每次迭代都排序），反而由于迭代深度太浅，排序不好反而会降低搜索速度。
			candidates.sort(function (a, b) {
				if (ai.ChessMath.getInstance().equal(a.score, b.score)) {
					// 大于零是优势，尽快获胜，因此取步数短的
					// 小于0是劣势，尽量拖延，因此取步数长的
					if (a.score >= 0) {
						if (a.step !== b.step) return a.step - b.step;
						else return b.score - a.score; // 否则 选取当前分最高的（直接评分)
					}
					else {
						if (a.step !== b.step) return b.step - a.step;
						else return b.score - a.score;// 否则 选取当前分最高的（直接评分)
					}
				}
				else return (b.score - a.score);
			})

			let result = candidates[0];
			result.min = Math.min.apply(Math, result.steps.map(d => d.score));
			console.log("选择节点：" + candidates[0] + ", 分数:" + result.score.toFixed(3) + ", 步数:" + result.step + ', 最小值：' + result.min);
			let time = ((+new Date()) - this.start) / 1000;
			console.log('搜索节点数:' + this.count + ',AB剪枝次数:' + this.ABcut + ', PV剪枝次数:' + this.PVcut);
			console.log('搜索缓存:' + '总数 ' + this.cacheCount + ', 命中率 ' + (this.cacheGet / this.cacheCount * 100).toFixed(3) + '%, ' + this.cacheGet + '/' + this.cacheCount);
			//注意，减掉的节点数实际远远不止 ABcut 个，因为减掉的节点的子节点都没算进去。实际 4W个节点的时候，剪掉了大概 16W个节点
			console.log('当前统计：' + this.count + '个节点, 耗时:' + time.toFixed(2) + 's, NPS:' + Math.floor(this.count / time) + 'N/S');
			console.log("===============统计表===============")
			this.board.statistic.print(candidates);
			return result
		}

		public deepAll(role, deep) {
			role = role || chess.ChessConst.role.com;
			deep = deep === undefined ? chess.ChessConst.config.searchDeep : deep;;
			const candidates = this.board.gen(role);
			return this.deeping(candidates, role, deep);
		}
	}
}